package com.hard;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created by Lxk on 2020/3/1.
 */
public class Solution123 {

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0 || prices.length == 1) {
            return 0;
        }
        for (int i = prices.length - 1; i > 0; i--) {
            prices[i] = prices[i] - prices[i - 1];
        }
        prices[0] = 0;
        List<Integer> tmp = new ArrayList<>();
        int sum = 0;
        for (int i = 0; i < prices.length; i++) {
            //System.out.print(prices[i]+" ");
            if (prices[i] >= 0) {
                sum += prices[i];
            } else {
                tmp.add(sum);
                sum = 0;
            }
        }
        if (sum > 0) {
            tmp.add(sum);
        }
        Collections.sort(tmp);
        //System.out.println("\n"+sum);
        if (tmp.size() > 1) {
            return tmp.get(tmp.size() - 1) + tmp.get(tmp.size() - 2);
        } else if (tmp.size() == 1) {
            return tmp.get(0);
        } else {
            return 0;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 2, 5, 7, 2, 4, 9, 0};
        Solution123 solution123 = new Solution123();
        System.out.println(solution123.maxProfit(arr));
    }
}
